|
Pattern search (PS) is a family of numerical optimization methods that do not require the gradient of the problem to be optimized. Hence PS can be used on functions that are not continuous or differentiable. Such optimization methods are also known as direct-search, derivative-free, or black-box methods. The name, pattern search, was coined by Hooke and Jeeves.〔 An early and simple PS variant is attributed to Fermi and Metropolis when they worked at the Los Alamos National Laboratory as described by Davidon 〔 who summarized the algorithm as follows: == Convergence == A convergent pattern-search method was proposed by Yu, who proved that it converged using the theory of positive bases.〔 *Yu, Wen Ci. 1979. “Positive basis and a class of direct search techniques”. ''Scientia Sinica'' (Kexue'' ): 53—68. *Yu, Wen Ci. 1979. “The convergent property of the simplex evolutionary technique”. ''Scientia Sinica'' (Kexue'' ): 69–77.〕 Later, Torczon, Lagarias, and coauthors,〔〔 used positive-basis techniques to prove the convergence of another pattern search method, on a specific class of functions. Outside of such classes, pattern search is a heuristic that can provide useful approximate solutions for some problems, but can fail on others. Outside of such classes, pattern search is not an iterative method that converges to a solution; indeed, pattern search methods can converge to non-stationary points on some relatively tame problems.〔 * Powell, Michael J. D. 1973. ”On Search Directions for Minimization Algorithms.” ''Mathematical Programming'' 4: 193—201.〕〔 * (algorithm summary online).〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pattern search (optimization)」の詳細全文を読む スポンサード リンク
|